#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include <string>
#include <cmath>
#include <iomanip> // 用于格式化输出
using namespace std;

// 打印邻接矩阵
void Print_Graph(const vector<vector<int>>& graph, const string& V_name) {
    int V = V_name.size(); // 顶点的数量
    cout << "对应矩阵为：\n";
    cout << "    "; // 顶部的空格用于对齐列标题
    for (int i = 0; i < V; i++) {
        cout << setw(4) << V_name[i]; // setw(4) 用于设置宽度，保持列对齐
    }
    cout << "\n";

    for (int i = 0; i < V; i++) {
        cout << setw(4) << V_name[i]; // 行标题
        for (int j = 0; j < V; j++) {
            if (graph[i][j] == 0) {
                cout << setw(4) << "0"; // setw(4) 用于设置宽度，保持列对齐
            }
            else if (graph[i][j] == INT_MAX) {
                cout << setw(4) << "∞"; // setw(4) 用于设置宽度，保持列对齐
            }
            else {
                cout << setw(4) << graph[i][j]; // setw(4) 用于设置宽度，保持列对齐
            }
        }
        cout << "\n";
    }
}

//利用普里姆算法，求最小生成树



int main()
{
    int V, E;//顶点与边数
    cin >> V >> E;

    string V_name; // 顶点的名字
    cin >> V_name;

    //利用vector来进行存储
   // 构建邻接矩阵,并初始化为0
    vector<vector<int>> graph(V,vector<int>(V, INT_MAX));
    // 初始化邻接矩阵的对角线元素为0
    for (int i = 0; i < V; i++) {
        graph[i][i] = 0;
    }

    //给边加上权重
    for (int i = 0; i < E; i++) {
        string u;
        int weight;
        cin >> u >> weight;
        int u_index = u[0] - 'A';
        int v_index = u[1] - 'A';
        graph[u_index][v_index] = weight;
        graph[v_index][u_index] = weight; // 无向图，所以需要添加两个方向的边
    }
    //打印显示
    // 打印邻接矩阵
    Print_Graph(graph, V_name);

    //调用普里姆算法，求最小生成树

}